//
//  ParallelMinCut.h
//  Min-Cut
//
//  Created by Emanuele Vespa on 5/9/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#ifndef Min_Cut_ParallelMinCut_h
#define Min_Cut_ParallelMinCut_h



#endif


#include "MultiGraph.h"
#include <tbb/tbb.h>
#include <sched.h>
#include <cmath>



// TASK CLASS DEFINITION


class MinCutRun: public tbb::task {
    
    
public:
    
    MultiGraph& g; // reference to the original copy of the graph
    MultiGraph ** min_cut; // working copy of the graph
    int partial_minimum; 
    
    int num_runs; // number of runs to be executed by this task
    int task_id; // id of the current task
    
    MinCutRun(MultiGraph& _in, MultiGraph  ** _min_cut, int _num_runs, int _task_id): g(_in), min_cut(_min_cut) {
        
        
        partial_minimum = 1000000000;
        num_runs = _num_runs;
        task_id = _task_id;
        
    }
    
    tbb::task* execute() { // tbb overloaded method, contains the actual code of the task to be executed 
        
#ifndef __APPLE__
        
        cpu_set_t  mask;
        CPU_ZERO(&mask);
        
        for(int i = 0; i < 8; i++) CPU_SET(i, &mask);
        sched_setaffinity(0, sizeof(mask), &mask);
#endif
        
        tbb::tick_count s, e;
        
        unsigned short seed[3];
        
        // seed initialization as a function of time and task id
        
        seed[0] = time(NULL);
        seed[1] = task_id;
        seed[2] = log((time(NULL) * exp(task_id)));
        

        *min_cut = new MultiGraph(g);
        
        
        (*min_cut)->KargerMinCut(num_runs, seed);
        
        
                                
        
        return NULL;
        
    }
    
    
};




// ROOT TASK CLASS DEFINITION

class MinCutRoot : public tbb::task {
        
    
public:
    
    // variables
    MultiGraph & original; // Reference to the original copy of the graph

    int num_threads; 
    int num_runs;
    
    tbb::task_list list;
    
    
    // methods
    
    MinCutRoot(MultiGraph &_original): original(_original){
        
        
        
        num_threads = tbb::task_scheduler_init::default_num_threads();
        num_runs = (original.vertexNum * original.vertexNum) / num_threads;
        
      
        
    }
    
    
    MinCutRoot(MultiGraph &_original, int _num_threads): original(_original){
        
        
        num_threads = _num_threads;
        num_runs = (original.vertexNum * original.vertexNum) / num_threads;
        
        
        
    }

    
    
    tbb::task * execute(){
        
        vector<MultiGraph**>  partial_min_cuts; // partial results vector of pointer
        int min = 10000000;
        int min_index;
        
        
        set_ref_count(1);
        
        for (int i = 0 ; i < num_threads; i++) {
            
            MultiGraph ** ptr = new MultiGraph*;
            
            MinCutRun& run = *new ( allocate_child() ) MinCutRun( original, ptr, num_runs, i); // Child task allocation
            
            partial_min_cuts.push_back(ptr);    // 
            
            list.push_back(run); // Push child task in the list of task 
            
            increment_ref_count();

        }
        
        
        
        spawn(list);
        
        task::wait_for_all();
        
    
        
        
        for( int i = 0; i < num_threads; i++ ){ // Extract minimum between partial results
            
            if ((*partial_min_cuts[i])->cut_weight < min){
                
                min_index = i;
                min = (*partial_min_cuts[i])->cut_weight;
                
            }
            
        }
        
        
        original.copy(*(*(partial_min_cuts[min_index]))); 
        
        cout << endl;

        
        return NULL;
        
    }
    
};


// METHOD FOR INVOKING THE PARALLEL EXECUTION OF KARGER ALGORITHM

int MultiGraph::ParallelKarger(){ 
    
    
    
    MultiGraph * min_cut;
    min_cut = new MultiGraph;
    
    
    MinCutRoot& r = * new ( tbb::task::allocate_root()) MinCutRoot(*this);
    
    tbb::task::spawn_root_and_wait(r);
        
    
    return 1;
    
}



// METHOD FOR INVOKING THE PARALLEL EXECUTION OF KARGER ALGORITHM, SPECIFYING THE NUMBER OF THREADS

int MultiGraph::ParallelKarger(int num_threads){
    
    
    
    MultiGraph * min_cut;
    min_cut = new MultiGraph;
    
    
    tbb::task_scheduler_init init(num_threads);
    
    
    MinCutRoot& r = * new ( tbb::task::allocate_root()) MinCutRoot(*this, num_threads);
    
    
    
    tbb::task::spawn_root_and_wait(r);
    
    
    
    return 1;
    
}








